/*--------------------------------------------------------------------

       +---------------------------------------------------+
       |                                                   |
       |   CYK/MEMBERSHIP                      ALGORITHM   |
       |                                                   |
       +---------------------------------------------------+


--------------------------------------------------------------------*/

 # include <stdio.h>
 # include <dir.h>

 struct prod {
               char sym , production[10] ;
              } ;

 struct var {
              char name[5] ;
             } ;

 struct arr {
              char elt , map[5] , string[10] ;
             } ;

 struct file {
               char fname[15] ;
              } ;

 struct prod prodn[20] ;
 struct var vars[20] , terms[20] ;
 struct arr map[20] ;
 struct ffblk fil ;
 struct file files[11] , table[20][20] ;
 int prodns = 0 , no_vars = 0 , no_terms = 0 , len = 0 ;
 char startsym , ipstr[50] ;

 # include <pop.c>

 int read_file (char fname[])
  {
    FILE *fp ;
    char string[80] , temp[5] ;
    int i , j ;

    if (( fp = fopen (fname,"r")) == NULL )
      return (-1) ;
    fgets (string,80,fp) ;
    while ( !feof(fp) )
     {
       for ( i = 0 ; string[i] == ' ' ; i++ ) ;
       switch ( string[i] )
        {
          case 'S' : for ( ; string[i] != '=' ; i++ ) ;
                     i++ ;
                     for ( ; string[i] == ' ' ; i++ ) ;
                     startsym = string[i] ;
                     break ;
          case 'V' : for ( ; string[i] != '{' ; i++ ) ;
                     i++ ;
                     for ( ; string[i] != '}' ; )
                      {
                        if ( string[i] == ',' )
                          i++ ;
                        for ( j = 0 ; (string[i] != '}') && (string[i] != ',') ; j++ , i++ )
                          vars[no_vars].name[j] = string[i] ;
                        vars[no_vars++].name[j] = '\0' ;
                       }
                     break ;
          case 'T' : for ( ; string[i] != '{' ; i++ ) ;
                     i++ ;
                     for ( ; string[i] != '}' ; )
                      {
                        if ( string[i] == ',' )
                          i++ ;
                        for ( j = 0 ; (string[i] != '}') && (string[i] != ',') ; j++ , i++ )
                          terms[no_terms].name[j] = string[i] ;
                        terms[no_terms++].name[j] = '\0' ;
                       }
                     break ;
          case '-' : i++ ;
                     for ( ; string[i] == ' ' ; i++ ) ;
                     prodn[prodns].sym = string[i] ;
                     for ( ; string[i] != '>' ; i++ ) ;
                     i++ ;
                     for ( ; string[i] == ' ' ; i++ ) ;
                     for ( ; string[i] != '.' ; )
                      {
                        if ( string[i] == '|' )
                         {
                           i++ ;
                           prodn[prodns].sym = prodn[prodns-1].sym ;
                          }
                        for ( j = 0 ; ( string[i] != '.' ) && (string[i] != '|') ; j++ , i++ )
                          prodn[prodns].production[j] = string[i] ;
                        prodn[prodns++].production[j] = '\0' ;
                       }
                     break ;
          default  : break ;
         }
       fgets (string,80,fp) ;
      }
   }

 display ()
  {
    int i ;

    for ( i = 0 ; i < prodns ; i++ )
     {
       printf ("\n               %c -> ",prodn[i].sym) ;
       printf ("%s",prodn[i].production) ;
      }
   }

 initialize_table ()
  {
    int i , j ;

    for ( i = 0 ; i < 20 ; i++ )
      for ( j = 0 ; j < 20 ; j++ )
        strcpy (table[i][j]," ") ;
   }

 get_input_string (int BACK)
  {
    clear_rect_a (1,1,25,80,BACK) ;
    dbox (1,1,24,79) ;
    clear_rect_a (12,5,2,70,15) ;
    dbox (12,5,2,70) ;
    i_shadow2 (12,5,2,70,7) ;
    pstr_a (13,10,"Input String :",15) ;
    gotoxy (25,13) ;
    gets (ipstr) ;
    len = strlen (ipstr) ;
    clear_rect_a (1,1,25,80,15) ;
   }

 validate_ip_string ()
  {
    int i , j , found = 0 ;

    for ( i = 0 ; i < len ; i++ )
     {
       for ( j = 0 ; j < no_terms ; j++ )
         if ( terms[j].name[0] == ipstr[i] )
           found = 1 ;
       if ( found == 0 )
         return (-1) ;
       found = 0 ;
      }
   }

 fill_table ()
  {
    int i , j , x ;

    for ( i = 0 , x = len ; i < len ; i++ , x-- )
      for ( j = 0 ; j < x ; j++ )
        strcpy (table[i][j],ipstr[i]) ;
   }

 main (int argc,char *argv[])
  {
    char str[15] ;
    int i , flines = 0 , BACK = 32 ;

    if ( ( argc == 2 ) && ( strcmp (argv[1],"/C") == 0 ) )
      BACK = 23 ;

    clear_rect_a (1,1,25,80,BACK) ;
    dbox (1,1,24,79) ;
    cattrib_rect (2,25,4,30,15) ;
    dbox (2,25,4,30) ;
    i_shadow2 (2,25,4,30,7) ;
    pstr_a (3,28,"CYK/MEMBERSHIP  ALGORITHM",15) ;
    pcpy (5,31) ;

    if ( argc == 1 )
      i = findfirst ("*.CYK",&fil,32) ;
    if ( ( argc == 2 ) && ( strcmp (argv[1],"/C") ) == 0 )
      i = findfirst ("*.CYK",&fil,32) ;
    if ( ( argc == 2 ) && ( strcmp (argv[1],"/C") ) != 0 )
      i = findfirst (argv[1],&fil,32) ;
    if ( argc == 3 )
      i = findfirst (argv[1],&fil,32) ;
    while ( ( i == 0 ) && ( flines < 10 ) )
     {
       strcpy (files[flines++].fname,fil.ff_name) ;
       i = findnext (&fil) ;
      }

    if ( flines == 0 )
     {
       cattrib_rect (10,30,2,17,BACK) ;
       dbox (10,30,2,17) ;
       i_shadow2 (10,30,2,17,7) ;
       pstr_a (11,31,"No Entries Found",15) ;
       getch () ;
       clear_rect_a (1,1,25,80,15) ;
       return ;
      }

    cattrib_rect (10,30,flines+1,15,BACK) ;
    dbox (10,30,flines+1,15) ;
    i_shadow2 (10,30,flines+1,15,7) ;
    i = popup (11,31,flines,BACK) ;
    strcpy (str,files[i].fname) ;
    i = read_file (str) ;
    if ( i == -1 )
     {
       clear_rect_a (1,1,25,80,15) ;
       return ;
      }

    clear_rect_a (1,1,25,80,15) ;
    printf ("     The Original Productions are as follows :\n") ;

    display () ;

    printf ("\n\n                         Press Any Key To Continue " ) ;
    textattr (0x8F) ;
    cprintf ("...") ;
    getch () ;
    textattr (15) ;

    initialize_table () ;

    get_input_string (BACK) ;

    if ( validate_ip_string () == -1 )
      printf ("\n\n     The Input String Contains Invalid Terminals !") ;
   }
